#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5+5;
int cnt[maxn], prefix[maxn];
int t, n;


void dfs(int dep, int x, int sum, int mul){
	// 剪枝 1
	if (mul > 1e5) {
		return;
	}
	if (dep==n+1) {
		cnt[mul]++;	
		return;
	}
	// 剪枝 2, 求出了 上限
	int up = pow(1e5/mul, 1.0/(n-dep+1)) + 5;
	// 剪枝3 设置了 下限 因为 假设为 递增了, 就防止了出现重复的情况
	for (int i=x+1;i < (dep==n?sum:up);i++) {
		dfs(dep+1, i, sum+i, mul*i);
	}
}


void solve(){
	cin >> t >> n;
	dfs(1, 0, 0, 1);
	for (int i=1;i<=1e5;i++) {
		prefix[i] = prefix[i-1]+cnt[i];
	}
	int l, r;
	while(t--){
		cin >> l >> r;
		cout << prefix[r]-prefix[l-1]<<'\n';
	}
}


signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
